package com.cdream.basic.algorithm.leetcode.tree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Question103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root==null){
            return new LinkedList<>();
        }
        List<List<Integer>> res = new LinkedList<>();
        Deque<TreeNode> nodeQueue = new LinkedList<>();

        nodeQueue.offer(root);
        int count = 1;
        boolean isLeft = true;
        while (!nodeQueue.isEmpty()){
            List<Integer> ele = new LinkedList<>();
            // 1. 计一下当前层有几个，给poll出来装到结果集里面
            int k = count;
            count = 0;
            for (int i = 0; i < k; i++) {
                TreeNode t = nodeQueue.poll();

                if (isLeft){
                    if (t.left!=null){
                        nodeQueue.offer(t.left);
                        count++;
                    }
                    if (t.right!=null){
                        nodeQueue.offer(t.right);
                        count++;
                    }
                }else {
                    if (t.right!=null){
                        nodeQueue.offer(t.right);
                        count++;
                    }
                    if (t.left!=null){
                        nodeQueue.offer(t.left);
                        count++;
                    }
                }
                ele.add(t.val);
            }
            isLeft = !isLeft;
            res.add(ele);
        }
        return res;
    }

    public static void main(String[] args) {
        LinkedList<Object> queue = new LinkedList<>();

        queue.push(1);
        queue.push(2);
        queue.push(3);
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.pop());
    }
}
